{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Final Prices With a Special Discount in a Shop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: finalPrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #商品折扣后的最终价格"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>prices</code>&nbsp;，其中&nbsp;<code>prices[i]</code>&nbsp;是商店里第&nbsp;<code>i</code>&nbsp;件商品的价格。</p>\n",
    "\n",
    "<p>商店里正在进行促销活动，如果你要买第&nbsp;<code>i</code>&nbsp;件商品，那么你可以得到与 <code>prices[j]</code> 相等的折扣，其中&nbsp;<code>j</code>&nbsp;是满足&nbsp;<code>j &gt; i</code>&nbsp;且&nbsp;<code>prices[j] &lt;= prices[i]</code>&nbsp;的&nbsp;<strong>最小下标</strong>&nbsp;，如果没有满足条件的&nbsp;<code>j</code>&nbsp;，你将没有任何折扣。</p>\n",
    "\n",
    "<p>请你返回一个数组，数组中第&nbsp;<code>i</code>&nbsp;个元素是折扣后你购买商品 <code>i</code>&nbsp;最终需要支付的价格。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>prices = [8,4,6,2,3]\n",
    "<strong>输出：</strong>[4,2,4,2,3]\n",
    "<strong>解释：</strong>\n",
    "商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。\n",
    "商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。\n",
    "商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。\n",
    "商品 3 和 4 都没有折扣。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>prices = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[1,2,3,4,5]\n",
    "<strong>解释：</strong>在这个例子中，所有商品都没有折扣。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>prices = [10,1,1,6]\n",
    "<strong>输出：</strong>[9,0,1,6]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= prices[i] &lt;= 10^3</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [final-prices-with-a-special-discount-in-a-shop](https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [final-prices-with-a-special-discount-in-a-shop](https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,4,6,2,3]', '[1,2,3,4,5]', '[10,1,1,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        for i in range(len(prices)-1):\n",
    "            for j in range(i+1,len(prices)):\n",
    "                if prices[j] <= prices[i]:\n",
    "                    prices[i] -= prices[j]\n",
    "                    break\n",
    "        return prices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        ans = list()\n",
    "        for i, price in enumerate(prices):\n",
    "            for j in prices[i+1:]:\n",
    "                if price >= j:\n",
    "                    ans.append(price - j)\n",
    "                    break\n",
    "            if len(ans) == i:\n",
    "                ans.append(price)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        for i in range(len(prices)-1):\n",
    "            for j in range(i+1,len(prices)):\n",
    "                if prices[j] <= prices[i] and prices[j] != 0:\n",
    "                    prices[i] -= prices[j]\n",
    "                    break\n",
    "        return prices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        n = len(prices)#数据长度\n",
    "        stack, res = [], prices.copy()#存index的空栈和拷贝\n",
    "        for i in range(n):\n",
    "            while stack and prices[stack[-1]] >= prices[i]:#栈非空且栈对应元满足出栈条件\n",
    "                res[stack[-1]] -= prices[i] #出栈数算折扣\n",
    "                stack.pop() #出栈\n",
    "            stack.append(i) #进栈\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        def discount(index,i):\n",
    "            for j in range(index+1,len(prices)):\n",
    "                if prices[j]<=i:\n",
    "                    return prices[j]\n",
    "            return 0\n",
    "        return [i-discount(index,i) for index,i in enumerate(prices)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        r_ans = [-1] * len(prices)\n",
    "        for i in range(len(prices)):\n",
    "            while stack and prices[stack[-1]] >= prices[i]:\n",
    "                pos = stack.pop(-1)\n",
    "                r_ans[pos] = prices[pos] - prices[i]\n",
    "            stack.append(i)\n",
    "        r_ans = [r_ans[i] if r_ans[i] != -1 else prices[i] for i in range(len(prices))]\n",
    "        return r_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        m = SortedDict()\n",
    "        ans = prices[::]\n",
    "        for i in range(len(prices)-1, -1, -1):\n",
    "            key_idx = m.bisect_right(prices[i])\n",
    "            min_idx = 0x7fffffff\n",
    "\n",
    "            vals = m.values()\n",
    "            for idx in range(key_idx):\n",
    "                min_idx = min(min_idx, vals[idx])                \n",
    "\n",
    "            if min_idx != 0x7fffffff:\n",
    "                ans[i] -= prices[min_idx]\n",
    "            m[prices[i]] = i\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        # n = len(prices)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if prices[j] <= prices[i]:\n",
    "        #             prices[i] = prices[i] -prices[j]\n",
    "        #             break\n",
    "        # return prices\n",
    "\n",
    "        n = len(prices)\n",
    "        for idx in range(n):\n",
    "            j = idx + 1\n",
    "            while j < n:\n",
    "                if prices[idx] >= prices[j]:\n",
    "                    prices[idx] -= prices[j]\n",
    "                    break\n",
    "                else:\n",
    "                    j += 1\n",
    "        return prices\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        small = [0]\n",
    "        length = len(prices)\n",
    "        answer = [0]*length\n",
    "        for i in range(length-1,-1,-1):\n",
    "            if len(small)==1:\n",
    "                small.append(prices[i])\n",
    "                answer[i] = prices[i]\n",
    "            else:\n",
    "                while len(small) > 1 and prices[i]<small[-1]:\n",
    "                    small.pop()\n",
    "                answer[i] = prices[i]-small[-1]\n",
    "                small.append(prices[i])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        returnList = []\n",
    "        length = len(prices)\n",
    "        for i in range(length - 1):\n",
    "            for j in range(i + 1, length):\n",
    "                if prices[i] >= prices[j]:\n",
    "                    p = prices[i] - prices[j]\n",
    "                    returnList.append(p)\n",
    "                    break\n",
    "            else:\n",
    "                returnList.append(prices[i])\n",
    "        returnList.append(prices[i + 1])\n",
    "        return returnList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        # 单调栈\n",
    "        ans = [0] * len(prices)\n",
    "        st = []\n",
    "        for i, j in enumerate(prices):\n",
    "            while st and prices[st[-1]] >= j:\n",
    "                x = st.pop()\n",
    "                ans[x] = prices[x] - j\n",
    "            st.append(i)\n",
    "        while st:\n",
    "            x = st.pop()\n",
    "            ans[x] = prices[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        ### 单调栈，右小，则单调增\n",
    "        if not prices or len(prices) <= 1: return [] \n",
    "\n",
    "        ans = [0]*len(prices)\n",
    "        stack = [0]\n",
    "        \n",
    "        for i in range(len(prices) - 1, -1, -1): #reversed(prices)\n",
    "            p = prices[i]\n",
    "            print(i,p,stack)\n",
    "            while len(stack)>1 and stack[-1] > p: #不满足单调增，则出栈\n",
    "                stack.pop()\n",
    " \n",
    "            final_p = p-stack[-1]\n",
    "            ans[i] = final_p\n",
    "            stack.append(p) #入栈\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # for i in range(len(prices)):\n",
    "        #     while stack and prices[stack[-1]]>=prices[i]:\n",
    "        #         cur=stack.pop()\n",
    "        #         ans[cur]=prices[cur]-prices[i]\n",
    "        #     stack.append(i)\n",
    "        # for i in stack:\n",
    "        #     ans[i]=prices[i]\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        ### 暴力\n",
    "        # ans = list(prices)\n",
    "        # n = len(prices)\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         if prices[j] <= prices[i]:\n",
    "        #             ans[i] = prices[i] - prices[j]\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 题目要求对于数组中的每个元素，在其后面找到第一个比它小的元素，如果找到了，则将其减去该元素，否则不打折。\n",
    "\n",
    "# 最小下标指的是在数组中，满足条件的元素中下标最小的那个。也就是说，如果有多个元素满足条件，那么选择下标最小的那个。\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        # n = len(prices)\n",
    "        # ans = [0] * n\n",
    "        # st = [0]\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     p = prices[i]\n",
    "        #     while len(st) > 1 and st[-1] > p:\n",
    "        #         st.pop()\n",
    "        #     ans[i] = p - st[-1]\n",
    "        #     st.append(p)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        ls=[]\n",
    "        lenth=len(prices)\n",
    "        for i in range(lenth):\n",
    "            maxi=0\n",
    "            # print(prices[i])\n",
    "            if i+1!=lenth:\n",
    "                for j in range(i+1,lenth):\n",
    "                    print(j)\n",
    "                    if maxi<j and prices[j]<=prices[i]:\n",
    "                        maxi=j\n",
    "                        break\n",
    "                        # print(maxi)\n",
    "                if maxi:\n",
    "                    ls.append(prices[i]-prices[j])\n",
    "                else:\n",
    "                    ls.append(prices[i])\n",
    "            else:\n",
    "                ls.append(prices[i])\n",
    "        return ls\n",
    "\n",
    "# class Solution:\n",
    "#     def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "#         ls=[]\n",
    "#         lenth=len(prices)\n",
    "#         for i in range(lenth):\n",
    "#             maxi=0\n",
    "#             if i+1!=lenth:\n",
    "#                 for j in range(i+1,lenth):\n",
    "#                     if maxi<j and prices[j]<=prices[i]:\n",
    "#                         maxi=j\n",
    "#                         break  # 找到第一个满足条件的 j 就可以退出循环了\n",
    "#                 if maxi:\n",
    "#                     ls.append(prices[i]-prices[maxi])\n",
    "#                 else:\n",
    "#                     ls.append(prices[i])\n",
    "#             else:\n",
    "#                 ls.append(prices[i])\n",
    "#         return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        # 单调栈——顺序写法\n",
    "\n",
    "        n = len(prices)\n",
    "        ans = [0] * n\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            p = prices[i]\n",
    "            while stack and p <= prices[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = prices[idx] - p\n",
    "            stack.append(i)\n",
    "            ans[i] = p\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        ans = prices\n",
    "        st = []\n",
    "        for i, p in enumerate(prices):\n",
    "            while st and p <= prices[st[-1]]:\n",
    "                j = st.pop()\n",
    "                ans[j] = prices[j] - p\n",
    "            st.append(i)\n",
    "\n",
    "        return ans\n",
    "                                                                                                                                                                                                                                                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def finalPrices(self, prices: List[int]) -> List[int]:\n",
    "        ans = prices.copy()\n",
    "        st = []\n",
    "        for i, val in enumerate(prices):\n",
    "            while st and val <= prices[st[-1]]:\n",
    "                ans[st.pop()] -= val\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
